package com.kavinz.algo.stack;

import com.kavinz.algo.list.DoublyLinkedList;

public class LinkedListStack<E> {

	// internal presentation of the data in Stack
	DoublyLinkedList<E> list = new DoublyLinkedList<E>();

	public void push(E token) {
		list.add(token);
	}

	public E peek() {
		return list.get(list.size() - 1);
	}

	public E pop() {
		return list.remove(list.size() - 1);
	}

	public E popBottom() {
		return list.remove(0);
	}

	public int size() {
		return list.size();
	}

	public boolean isEmpty() {
		return list.isEmpty();
	}

	/**
	 * <Cracking the coding interview><br>
	 * Exercise 3.6<br>
	 * Write a program to sort a stack in ascending order You should not make
	 * any assumptions about how the stack is implemented The following are the
	 * only functions that should be used to write this program: push | pop |
	 * peek | isEmpty
	 */
	public LinkedListStack<E> sort() {
		LinkedListStack<E> result = new LinkedListStack<E>();
		E tmp = null;
		while (!this.isEmpty()) {
			if (result.isEmpty()
					|| Integer.parseInt(this.peek().toString()) > Integer
							.parseInt(result.peek().toString()))
				result.push(this.pop());
			else {
				// save the abnormal value
				tmp = this.pop();
				// put back
				while (!result.isEmpty())
					this.push(result.pop());
				// put in the abnormal value to result
				result.push(tmp);
			}
		}
		return result;
	}

	public static void main(String[] args) {

		LinkedListStack<String> stack = new LinkedListStack<String>();

		stack.push("5");
		stack.push("3");
		stack.push("7");
		stack.push("9");
		stack.push("1");
		stack.push("2");

		System.out.println(stack.sort());
		// System.out.println("pop:" + stack.pop() + ";size:" + stack.size());
		// System.out.println("pop:" + stack.pop() + ";size:" + stack.size());
		// System.out.println("pop:" + stack.pop() + ";size:" + stack.size());
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append("head");
		for (int i = 0; i < list.size(); i++) {
			sb.append("--->").append(list.get(i));
		}
		sb.append("--->end");
		return sb.toString();
	}

}
